package main

import "fmt"

/*
你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字： '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' 。每个拨轮可以自由旋转：例如把 '9' 变为 '0'，'0' 变为 '9' 。每次旋转都只能旋转一个拨轮的一位数字。

锁的初始数字为 '0000' ，一个代表四个拨轮的数字的字符串。

列表 deadends 包含了一组死亡数字，一旦拨轮的数字和列表里的任何一个元素相同，这个锁将会被永久锁定，无法再被旋转。

字符串 target 代表可以解锁的数字，你需要给出解锁需要的最小旋转次数，如果无论如何不能解锁，返回 -1 。

作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/queue-stack/kj48j/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
*/

func openLock(deadends []string, target string) int {
	visited := make(Set)
	deadSet := make(Set)
	for _, deadCode := range deadends {
		deadSet.Add(deadCode)
	}
	if deadSet.HasKey(target) || deadSet.HasKey("0000") {
		return -1
	}
	return bfs(deadSet, target, visited)
}

type Set map[string]struct{}

func (s Set) Add(key string) {
	s[key] = struct{}{}
}

func (s Set) HasKey(key string) bool {
	_, exists := s[key]
	return exists
}

func bfs(deadSet Set, target string, visited Set) (step int) {
	startCode := "0000"
	if target == startCode {
		return 0
	}
	var queue []string
	queue = append(queue, startCode)
	visited.Add(startCode)
	for len(queue) != 0 {
		size := len(queue)
		for i := 0; i < size; i++ {
			code := queue[0]
			queue = queue[1:]
			if code == target {
				return
			}
			// 任意旋转其中一位数字一下
			for j, b := range code {
				newByte := b + 1
				if newByte > '9' {
					newByte = '0'
				}
				newCode := code[0:j] + string(newByte) + code[j+1:]
				if !visited.HasKey(newCode) && !deadSet.HasKey(newCode) {
					queue = append(queue, newCode)
					visited.Add(newCode)
				}
				newByte = b - 1
				if newByte < '0' {
					newByte = '9'
				}
				newCode = code[:j] + string(newByte) + code[j+1:]
				if !visited.HasKey(newCode) && !deadSet.HasKey(newCode) {
					queue = append(queue, newCode)
					visited.Add(newCode)
				}
			}
		}
		step++ // step+1，因为以上操作都是一步可达
	}
	return -1
}

func main() {
	deadends := []string{
		"0201", "0101", "0102", "1212", "2002",
	}
	target := "0202"
	fmt.Println(openLock(deadends, target))
}
